/*
 * Author: Wang Hsutung
 * Date: 2015/11/15
 * Locale: Wuhan, Hubei
 * Email: hsu[AT]whu.edu.cn
 */
#include <iostream>
#include <string>
#include <stack>

using namespace std;

struct node {
    char ch;
    node *left;
    node *right;

    node(char c, node *l = NULL, node *r = NULL) :
        ch(c), left(l), right(r) {}

    static void print(node *p, string prefix = "")
    {
        if (!p) {
            cout << "(null)" << endl;
            return;
        }
        cout << p->ch << endl;

        if (p->left || p->right) {
            cout << prefix << "├── ";
            print(p->left,  prefix + "│   ");
            cout << prefix << "└── ";
            print(p->right, prefix + "    ");
        }
    }
};

struct binTree {
    node *root;

    void print(void)
    {
        node::print(root);
    }

    void traverse(void)
    {
        if (root == NULL)
            return;

        std::stack<node*> nodeStack;
        std::stack<bool>   statStack; /* Whether a node is visited */
        nodeStack.push(root);
        statStack.push(0);

        while (!nodeStack.empty()) {
            node *p = nodeStack.top();
            nodeStack.pop();
            bool pc = statStack.top();
            statStack.pop();

            if (pc) {
                cout << p->ch << " ";
                continue;
            }

            if (p->right != NULL) {
                nodeStack.push(p->right);
                statStack.push(false);
            }
            nodeStack.push(p);
            statStack.push(true);
            if (p->left != NULL) {
                nodeStack.push(p->left);
                statStack.push(false);
            }
        }
        cout << endl;
    }
};

int main(int argc, char *argv[])
{
    binTree tree;
    tree.root = new node('+');
    tree.root->left = new node('*');
    tree.root->right = new node('/');
    tree.root->right->left = new node('4');
    tree.root->right->right = new node('5');
    tree.root->left->left = new node('1');
    tree.root->left->right = new node('^');
    tree.root->left->right->left = new node('2');
    tree.root->left->right->right = new node('3');

    tree.print();
    cout << "\nInorder form of the syntax tree above is: "
         << "(non-recursive implementation)\n" << endl;
    tree.traverse();
    return 0;
}
